package Leetcode;

import base.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 */
public class 力扣160_相交链表 {

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = b;

        ListNode a1 = new ListNode(1);
        ListNode b1 = new ListNode(2);
        a1.next = b1;
        b1.next = d;
        ListNode intersectionNode = getIntersectionNode(a, a1);
        System.out.println(intersectionNode.val);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while (headA != null || headB != null) {
            if (headA != null) {
                if (!set.add(headA)) {
                    return headA;
                }
                headA = headA.next;
            }
            if (headB != null) {
                if (!set.add(headB)) {
                    return headB;
                }
                headB = headB.next;
            }
        }
        return null;
    }
}
